using System;
using System.Collections;
using System.Text;

public class SudokuI7
{
    public int[] queryResults(int x, int[] qr)
    {
        pi = qi = -1;
        int i = qr[0] - 1, j = qr[1] - 1, k = i * N2 + j;
        x--;

        ms[k] = 1LU << x;
        rs[k] = x + 1;
        qi++;
        qx[qi] = x;
        qk[qi] = k;
        notify(k);

        if (qn < N2)
        {
            extend(x, k);
            qr[1] = N * (qn % N) + (qn / N) + 1;
            qr[0] = ++qn;
            return qr;
        }
    Loop:
        pi++;
        extend(qx[pi], qk[pi]);
        if (pi < qi)
            goto Loop;
    Check:
        done = false;
        single(asetsIQ, asets);
        single(rsetsIQ, rsets);
        single(csetsIQ, csets);
        checkSubs();
        checkPairs();
        if (pi < qi)
            goto Loop;
        if (done)
            goto Check;
        double best = double.MinValue, tt;
        int bestk = -1;
        for (k = N4_1; k >= 0; k--)
            if (rs[k] == 0 && (tt = N2 * Count(ms[k]) + (k / N2) + (k % N2) + rand.NextDouble()) >= best)
            {
                best = tt; bestk = k;
            }
        if (bestk >= 0)
            return new int[] { (bestk / N2) + 1, (bestk % N2) + 1 };
        return rs;
    }
    bool done;
    int qi, pi;
    int[] qx, qk, rs;
    ulong[] ms;

    void mask(ulong m, int k)
    {
        m = ms[k] & m;
        if (ms[k] == m)
            return;
        ms[k] = m;
        if (((m - 1) & m) == 0)
        {
            int x = GetX(m);
            rs[k] = x + 1;
            qi++;
            qx[qi] = x;
            qk[qi] = k;
        }
        notify(k);
        done = true;
    }

    void extend(int x, int k)
    {
        int i = k / N2, j = k % N2;
        ulong m = MASK ^ (1LU << x);
        foreach (int index in asets[i / N * N + j / N])
            if (rs[index] == 0 && index != k)
                mask(m, index);
        foreach (int index in rsets[i])
            if (rs[index] == 0 && index != k)
                mask(m, index);
        foreach (int index in csets[j])
            if (rs[index] == 0 && index != k)
                mask(m, index);
    }

    void notify(int k)
    {
        subsIQ.Add(subsOfk1[k]);
        subsIQ.Add(subsOfk2[k]);
        rsetsIQ.Add(k / N2);
        csetsIQ.Add(k % N2);
        asetsIQ.Add(k / N3 * N + k % N2 / N);
    }
    void checkSubs()
    {
        int i;
        while ((i = subsIQ.Next()) >= 0)
        {
            ulong m = 0LU;
            foreach (int mid in subs[i])
                m |= ms[mid];
            if (subsMask[i] != m)
            {
                subsMask[i] = m;
                foreach (int pid in pairsOfSubs[i])
                    pairsIQ.Add(pid);
            }
        }
    }
    void checkPairs()
    {
        int i;
        while ((i = pairsIQ.Next()) >= 0)
        {
            ulong m = 0LU;
            foreach (int sid in pairs[i])
                m |= subsMask[sid];
            if (pairsMask[i] != m)
            {
                pairsMask[i] = m;
                pairsMask[i ^ 1] = m;
                foreach (int sid in pairs[i ^ 1])
                    foreach (int mid in subs[sid])
                        if (rs[mid] == 0)
                            mask(m, mid);
            }
        }
    }

    ulong[] sms;
    void single(IQ iq, int[][] sets)
    {
        int a;
        while ((a = iq.Next()) >= 0)
        {
            int[] list = sets[a];
            for (int i = N2_1; i >= 0; i--)
                sms[i] = sms[i + 1] | ms[list[i]];
            ulong m = 0LU;
            for (int i = 0; i < N2; i++)
            {
                if (rs[list[i]] == 0 && (m | sms[i + 1]) != MASK)
                    mask((m | sms[i + 1]) ^ MASK, list[i]);
                m |= ms[list[i]];
            }
        }
    }
    Random rand = new Random();

    static int[][] subs, pairs, rsets, csets, asets, pairsOfSubs;
    static int[] subsOfk1, subsOfk2;
    ulong[] subsMask, pairsMask;
    IQ subsIQ, pairsIQ, rsetsIQ, csetsIQ, asetsIQ;
    static ulong MASK;
    static int N, N2, N3, N4, N2_1, N4_1, qn;
    public int[] initialize(int n)
    {
        qn = 1;
        N = n;
        N2 = n * n;
        N3 = N2 * n;
        N4 = N3 * n;
        N2_1 = N2 - 1;
        N4_1 = N4 - 1;
        MASK = 1LU << (N2_1);
        MASK = (MASK - 1) + MASK;
        int i, j, k, l, s, e, a, b;

        sms = new ulong[N2 + 1];

        subsIQ = new IQ(2 * N3);
        pairsIQ = new IQ(4 * N3);
        rsetsIQ = new IQ(N2);
        csetsIQ = new IQ(N2);
        asetsIQ = new IQ(N2);

        subs = new int[2 * N3][];
        subsMask = new ulong[2 * N3];
        pairsOfSubs = new int[2 * N3][];
        for (i = subs.Length - 1; i >= 0; i--)
        {
            subs[i] = new int[n];
            subsMask[i] = MASK;
            pairsOfSubs[i] = new int[2 * (n - 1)];
        }
        pairs = new int[4 * N3][];
        pairsMask = new ulong[4 * N3];
        for (i = pairs.Length - 1; i >= 0; i--)
        {
            pairs[i] = new int[n - 1];
            pairsMask[i] = MASK;
        }

        rsets = new int[N2][];
        csets = new int[N2][];
        asets = new int[N2][];
        for (i = N2_1; i >= 0; i--)
        {
            rsets[i] = new int[N2];
            csets[i] = new int[N2];
            asets[i] = new int[N2];
        }
        subsOfk1 = new int[N4];
        subsOfk2 = new int[N4];
        for (k = N4_1; k >= 0; k--)
        {
            i = k / N2;
            j = k % N2;
            rsets[i][j] = k;
            csets[j][i] = k;
            asets[i / n * n + j / n][(i % n) * n + (j % n)] = k;
            subsOfk1[k] = a = i * n + j / n;
            subsOfk2[k] = b = N3 + j * n + i / n;
            subs[a][j % n] = k;
            subs[b][i % n] = k;
        }
        int d = N3 << 1;
        int[] posp = new int[pairsOfSubs.Length];
        for (k = N3 - 1; k >= 0; k--)
        {
            i = k / n;
            j = k % n;
            a = k << 1;
            for (l = 0, s = i * n, e = s + n; s < e; s++)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
            a++;
            for (l = 0, s = i / n * N2 + j, e = s + N2; s < e; s += n)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
        }

        ms = new ulong[N4];
        for (i = N4_1; i >= 0; i--)
            ms[i] = MASK;

        rs = new int[N4];
        pi = qi = -1;
        qx = new int[N4];
        qk = new int[N4];
        return new int[] { 1, 1 };
    }

    static int Count(ulong m)
    {
        int ret = 0;
        while (m > 0)
        {
            ret += (int)(m & 1UL);
            m >>= 1;
        }
        return ret;
    }
    static int GetX(ulong m)
    {
        for (int q = 0; q < N2; q++)
            if ((m & (1LU << q)) != 0LU)
                return q;
        if (m == 0)
            throw new Exception();
        return -1;
    }
    class IQ
    {
        public IQ(int n)
        {
            q = new int[n];
            m = new bool[n];
            this.n = n;
        }
        int e = 0, i = 0, n;
        int[] q;
        bool[] m;
        public int Count { get { return i - e; } }
        public int Next()
        {
            if (e == i)
                return -1;
            int ret = q[e % n];
            m[ret] = false;
            e++;
            return ret;
        }
        public void Add(int a)
        {
            if (m[a])
                return;
            m[a] = true;
            q[i % n] = a;
            i++;
        }
    }
}
